package com.code.leetcode._202508;

import java.util.Arrays;

// 60 排列序列
public class GetPermutation {
    /**
     * 给出集合[1,2,3...,n],其所有元素共有n!种排列
     * 按大小顺序列出所有排列情况，并一一标记，当n==3时，所有排列如下：
     * 1、"123"
     * 2、"132"
     * 3、"213"
     * 4、"231"
     * 5、"312"
     * 6、"321"
     * 给定n和k，返回第k个排列
     * 示例1：输入：n=3,k=3
     * 输出："213"
     * 示例2:输入：n=4,k=9
     * 输出："2314"
     * 示例3:输入：n=3,k=1
     * 输出："123"
     ***/
    public static void main(String[] args) {
        GetPermutation g = new GetPermutation();
        System.out.println(g.getPermutation(4, 9));
    }

    /**
     * 数学+缩小问题规模
     * 要想解决本题，首先需要了解一个简单的结论：
     * 对于n个不同的元素(例如数1,2...,n)，他们可以组成的排列总数目为n!
     * 对于给定的n和k，我们不妨从左往右确定第k个排列中的每一个位置上的元素到底是什么。
     * 我们首先确定排列中的首个元素a1，根据上述的结论，我们可以知道：
     * 1、以1为a1的排列一共有(n-1)！个
     * 2、以2为a1的排列一共有(n-1)！个
     * ...
     * n、以n为a1的排列一共有(n-1)！个
     * 由于我们需要求出从小到大的第k个排列，因此：
     * 1、如果k<=(n-1)!，我们就可以确认排列的首个元素为1；
     * 2、如果(n-1)!<k<=2*(n-1)!，我们就可以确认排列的首个元素为1；
     * ...
     * n、如果(n-1)*(n-1)<k<=n*(n-1)!，我们就可以确认排列的首个元素为1；
     * 因此，第k个排列的首个元素就是
     * a1=(k-1)/(n-1)! +1
     * 其中|x|表示将x向下取整。
     * 当我们确定了a1后，如何使用相似的思路，确定下一个元素a2呢？我们考虑以a1为首个元素的所有排列：
     * 1、以[1,n]\a1最小的元素为a2的排列一共有(n-2)！个
     * 2、以[1,n]\a1次小的元素为a2的排列一共有(n-2)！个
     * ...
     * n、以[1,n]\a1最大的元素为a2的排列一共有(n-2)！个
     * 其中[1,n]\a1表示包含1,2,...n中除去a1以外元素的集合.这些片列从编号(a1-1)*(n-1)！开始，到a1*(n-1)!结束，
     * 总计(n-1)!个，因此第k个排列实际上就对应着这其中的第k'=(k-1)mod(n-1)!+1个排列。这样一来，我们就把原问题转化成
     * 了一个完全相同但规模减少1的子问题：
     * 求[1,n]\a1这n-1个元素组成的排列中，第k'小的排列
     * 算法
     * 设第k个排列为a1,a2,...,an，我们从左往右地确定每一个元素ai，我们用数组valid记录每一个元素是否被使用过，
     * 我们从小到大枚举i：
     * 1、我们已经使用过了i-1个元素，剩余n-i+1个元素未使用过，每一个元素作为ai都对应着(n-i)!个排列，总计(n-i+1)！个排列；
     * 2、因此在第k个排列中，ai即为剩余未使用过的元素中第(k=1)/(n-i)+1小的元素
     * 3、在确定了a1后，这n-i+1个元素的第k个排列，就等于ai之后跟着剩余n-i个元素的第(k-1)mod(n-i)!+1个排列
     * 在实际的代码中，我们可以首先将k的值减少1，这样可以减少运算，降低代码出错的概率，对应上述的后两步，即为：
     * 1、因此在第k个排列中，ai即为剩余未使用过的元素中k/(n-i)!+1小的元素
     * 2、在确定了ai后，这n-i+1个元素的第k个排列，就等于ai之后跟着剩余n-i个元素的第k mod(n-i)！个排列。
     * 实际上，这相当于我们将所有的排列从0开始进行编号。
     * *
     **/
    public String getPermutation(int n, int k) {
        int[] factorial = new int[n];
        factorial[0] = 1;
        //所有的i的阶乘的结果
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
        --k;
        StringBuffer ans = new StringBuffer();
        int[] valid = new int[n + 1];
        Arrays.fill(valid, 1);
        for (int i = 1; i <= n; i++) {
            int order = k / factorial[n - i] + 1;
            for (int j = 1; j <= n; j++) {
                order -= valid[j];
                if (order == 0) {
                    ans.append(j);
                    valid[j] = 0;
                    break;
                }
            }
            k %= factorial[n - i];
        }
        return ans.toString();
    }
}
